#!/usr/bin/env python3

def merge_sort(array, start=0, end=None):
    if end is None:
        end = len(array)

    if end - start <= 1:
        return

    middle = int((end + start) / 2)
    merge_sort(array, start, middle)
    merge_sort(array, middle, end)
    left_array = array[start : middle]
    right_array = array[middle : end]
    current_left = 0
    current_right = 0
    for index in range(start, end):
        is_left = False
        if current_left < len(left_array) and current_right < len(right_array):
            # Two array both have value
            is_left = left_array[current_left] < right_array[current_right]
        else:
            is_left = current_left < len(left_array)

        if is_left:
            array[index] = left_array[current_left]
            current_left += 1
        else:
            array[index] = right_array[current_right]
            current_right += 1



def _for_assert(array):
    merge_sort(array)
    assert 1 == array[0]
    assert 3 == array[2]
    assert 6 == array[5]
            
def test_merge_sort():
    array = [1, 2, 3, 4, 5, 6]
    _for_assert(array)
    _for_assert([6, 5, 4, 3, 2, 1])
    _for_assert([5, 3, 2, 6, 1, 4])
